package com.cet.algorithm.二叉树.二叉搜索树中的众数;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: cet-practice
 * @description: BST中的众数
 * @author: 陈恩涛
 * @create: 2023-04-05 19:47
 **/
public class LC501 {

    public static void main(String[] args) {

    }

    static List<Integer> list;

    static int maxCount;

    static int count;

    static TreeNode pre;

    static int[] findMode(TreeNode root) {
        list = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        findMode1(root);
        int[] result = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            result[i] = list.get(i);
        }
        return result;
    }

    static void findMode1(TreeNode root) {
        if (root == null) {
            return;
        }
        findMode1(root.left);

        if (pre != null && pre.val == root.val) {
            count ++;
        } else {
            count = 1;
        }

        // 更新结果以及maxCount
        if (count > maxCount) {
            list.clear();
            list.add(root.val);
            maxCount = count;
        } else if (count == maxCount) {
            list.add(root.val);
        }
        pre = root;

        findMode1(root.right);
    }
}
